/* CSP-201803P4 棋局评估（博弈、搜索）
在CSP-201803P4-state-encode.cpp基础上，还可继续探索：
1. 预先算出各状态得分并存到表中，输入棋局后编码为标识，可直接查分，即“打表”做法。
2. 对每个棋局计算出得分，绘制博弈图展现。
*/
#include <fstream>
#include <iostream>
#include <map>
#include <set>
using namespace std;

const int win_states[3][8] = {
  {}, // 保留0不用，可直接索引1、2方。
  { 0b010101000000000000, 0b000000010101000000, 0b000000000000010101,
    0b010000010000010000, 0b000100000100000100, 0b000001000001000001,
    0b010000000100000001, 0b000001000100010000
  }, // A(1=0b01) win
  { 0b101010000000000000, 0b000000101010000000, 0b000000000000101010,
    0b100000100000100000, 0b001000001000001000, 0b000010000010000010,
    0b100000001000000010, 0b000010001000100000
  }  // B(2=0b10) win
};

bool win(int x, int state){
  for(int i = 0; i < 8; ++i){
    if((win_states[x][i] & state) == win_states[x][i]){
      return true;
    }
  }
  return false;
}

map<int, int> scores; // 状态~得分表
map<int, set<int> > graph; // 博弈图

int check(int x, int state, int space){
  auto it = scores.find(state);
  if(it != scores.end()){
    return it->second;
  }
  const int y = (x == 1 ? 2 : 1);
  if(win(x, state)){
    return scores[state] = space + 1;
  }
  if(win(y, state)){ // 对方胜
    return scores[state] = -(space + 1);
  }
  const int INF = -9;
  int mx = INF;
  set<int> &st = graph[state];
  for(int i = 0, m = 0b11; i < 9; ++i, m <<= 2){
    if((state & m) == 0){ // 发现空白就递归搜索
      int sub_state = (state | (x << (i * 2)));
      if(st.find(sub_state) == st.end()){
        st.insert(sub_state);
      }
      mx = max(mx, -check(y, sub_state, space - 1)); // 对方的评分取负就是该局面我方评分
    }
  }
  return scores[state] = (mx == INF ? 0 : mx); // 若分数没有变动，双方都没取胜，平局。可胜可负。
}

void print_score_table(const char *filename){
  ofstream ofs(filename);
  int i = 0;
  for(auto &e : scores){
    if(i++ > 0){ ofs << ','; }
    if((i % 100) == 0){ ofs << '\n'; }
    ofs << '{' << e.first << ',' << e.second << '}';
  }
}

void print_game_graph(const char *filename){
  ofstream ofs(filename);
  ofs << "digraph {\n";
  ofs << "  rankdir=\"LR\";\n";
  for(auto &s : scores){
    ofs << "  " << s.first << " [label=\"" << s.first << ":" << s.second << "\"];\n";
  }
  for(auto gt = graph.begin(), ge = graph.end(); gt != ge; ++gt){
    const int u = gt->first;
    const set<int> &st = gt->second;
    for(int v : st){
      ofs << "  " << u << " -> " << v << ";\n";
    }
  }
  ofs << "}\n";
}

int main(){
  check(1, 0, 9);
  print_score_table("CSP-201803P4-state-score.txt");
  print_game_graph("CSP-201803P4-game-graph.dot");
}
